package com.dyl;

import java.util.Random;

public class QuickSort {
    public static void main(String[] args) {
        int[] num = {5, 3, 1, 2, 4, 6};
        quickSort(num, 0, num.length - 1);
        for (int i = 0; i < num.length; i++) {
            System.out.println(num[i]);
        }
    }

    public static void quickSort(int[] num, int left, int right) {
        if (left >= right) return;
        // 选择基准元素
        int baseIndex = new Random().nextInt(right - left + 1) + left;
        // 交换第一个元素和基准元素
        swap(num, baseIndex, left);
        int oldLeft = left;
        int oldRight = right;
        while (left < right) {
            while(right > left && num[right] >= num[left]) right--;
            while(left < right && num[left] <= num[right]) left++;
            swap(num, left, right);
        }
        swap(num, left, oldLeft);
        quickSort(num, oldLeft, left - 1);
        quickSort(num, left + 1, oldRight);
    }

    public static void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
}
